#include <iostream>
#define  maxsize 100
#include <ctime>
#include <cstdlib>
using namespace std;
int a[maxsize];
int n;
//插入排序
//1.直接插入排序  稳定
//2.二分插入排序   稳定
//3.希尔排序    不稳定

//交换排序
//1.冒泡排序   稳定
//双向冒泡排序 奇偶交换排序
//2.快速排序    不稳定
int Partion(int left,int right)
{
   int temp=a[left];
   int i=left,j=right;

   while(i<j)
   {
       while(a[j]>=temp&&i<j)//这边i<j不能少 因为外循环的i<j必须在执行完循环体一扁才会执行
       {
           j--;
       }
       a[i]=a[j];
       while(a[i]<=temp&&i<j)
       {
           i++;
       }
       a[j]=a[i];
   }
   a[i]=temp;
   return i;


}
void QuickSort(int left,int right)
{
    if(left>=right)
        return ;
     int pivot=Partion(left,right);  //确定枢纽位置
     QuickSort(left,pivot-1);  //划分左右继续排序
     QuickSort(pivot+1,right);
}


//选择排序
//1.堆排序     不稳定
//建立大根堆  //升序
void CreateHeap()
{
    for(int i=n/2;i>=1;i--)
    {
        for(int k=i*2;k<=n;k=k*2)
        {
            if(k+1<=n-1&&a[k+1]>a[k])
            {
                k++;
            }
            if(a[i]<a[k])
            {
                swap(a[i],a[k]);
                i=k; //i下移
            }
        }
    }
}

void AdjustHeap(int i,int last)
{
        for(int k=i*2;k<=last;k=k*2)
        {
            if(k+1<=last&&a[k+1]>a[k])
            {
                k++;
            }
            if(a[i]<a[k])
            {
                swap(a[i],a[k]);
                i=k; //i下移
            }
        }
}
void HeapSort()
{
    CreateHeap();//建立大根堆
    for(int i=n;i>=2;--i)
    {
        swap(a[1],a[i]);
        AdjustHeap(1,i-1);

    }
}




//应用从1亿个数中选取前100个最大的树
//2.简单选择   不稳定


//基数排序
//归并排序




//初始化数组
void initialHeapArray()
{
    srand((int)time(NULL));
    for(int i=1;i<=n;++i)
    {
        a[i]=(rand()%(100-1))+1;
    }
}
void printHeapArray()
{
    for(int i=1;i<=n;++i)
    {
        cout<<a[i]<<" ";
    }
}


//初始化数组
void initialArray()
{
    srand((int)time(NULL));
    for(int i=0;i<=n-1;++i)
    {
        a[i]=(rand()%(100-1))+1;
    }
}
void printArray()
{
    for(int i=0;i<=n-1;++i)
    {
        cout<<a[i]<<" ";
    }
}
int main() {


    cin>>n;
    initialArray();
    cout<<"Before:     ";
    printArray();
    cout<<endl;
//    QuickSort(0,n-1);
//    HeapSort();   //堆排序需要将数组改成从1到n
    cout<<"After:      ";
    printArray();
    cout<<endl;
    return 0;
}
